package LeetCode.exercise;

import java.util.*;

public class LC429 {
    static class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public static void main(String[] args) {
        Node node = new Node(1, new ArrayList<Node>());
        Node node1 = new Node(3, new ArrayList<>());
        Node node2 = new Node(2, new ArrayList<>());
        Node node3 = new Node(4, new ArrayList<>());
        Node node4 = new Node(5, new ArrayList<>());
        Node node5 = new Node(6, new ArrayList<>());
//        Node node6 = new Node(7);
        node.children.add(node1);
        node.children.add(node2);
        node.children.add(node3);
        node1.children.add(node4);
        node1.children.add(node5);
        LC429 lc429 = new LC429();
        System.out.println(lc429.levelOrder(node));
    }
    public List<List<Integer>> levelOrder(Node root) {
        if(root == null){
            return new ArrayList<>();
        }
        Deque<Node> queue = new LinkedList<>();
        List<List<Integer>> lists = new ArrayList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> thisList = new ArrayList<>();
            int size = queue.size();
            while (size-- > 0) {
                Node tmp = queue.poll();
                thisList.add(tmp.val);
                for (int j = 0; j < tmp.children.size(); j++) {
                    queue.offer(tmp.children.get(j));
                }
            }
            lists.add(thisList);
        }
        return lists;
    }
}
